Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Multimodal differential evolution algorithm for solving capacitated vehicle routing problem
Jian LIN, Jingxuan YE, Wenwen LIU, Xiaowen SHAO
Journal of Computer Applications    2023, 43 (7): 2248-2254.   DOI: 10.11772/j.issn.1001-9081.2022060812
Abstract198)   HTML7)    PDF (1138KB)(203)       Save

In Capacitated Vehicle Routing Problem (CVRP), the influence of uncertain factors including traffic congestion, resource supply and customer demand will easily make the single optimal solution infeasible or non-optimal. To solve this problem, a Multimodal Differential Evolution (MDE) algorithm was proposed to obtain multiple alternative vehicle routing schemes with similar objective values. Firstly, combined with the characteristics of CVRP, an efficient solution individual coding and decoding strategy was constructed, and the solution individual quality was improved using a repair mechanism. Secondly, in the framework of Differential Evolution (DE) algorithm, a dynamic radius niche generation method was introduced from the perspective of multimodal optimization, and the Jaccard coefficient was used to measure the similarity between solution individuals, which realized the calculation of the distance between solution individuals. Finally, the neighborhood search strategy was modified, and a multimodal optimal solution set was obtained using elite archiving and updating strategy. Simulation and analysis results based on typical datasets show that the average number of optimal solutions obtained by the proposed MDE algorithm reaches 1.743 4, and the deviation between the average optimal solution obtained by the proposed MDE algorithm and the known optimal solution is 0.03%, better than 0.8486 and 0.63% obtained by the DE algorithm. It can be seen that the proposed algorithm has high effectiveness and stability in solving CVRP, and can obtain multiple optimal solutions for CVRP simultaneously.

Table and Figures | Reference | Related Articles | Metrics